package Day2025_03_09;

import java.util.*;

public class LeetCode675 {
    int[] dx = {0, 0, -1, 1};
    int[] dy = {-1, 1, 0, 0};
    public int cutOffTree(List<List<Integer>> forest) {
        int m = forest.size(), n = forest.get(0).size();
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j++) {
                if (forest.get(i).get(j) > 1) list.add(new int[]{i, j});
            }
        }
        Collections.sort(list, (a, b) -> {
            return forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]);
        });
        int ex = 0, ey = 0;
        int sum = 0;
        for (int[] ret : list) {
            int a = ret[0], b = ret[1];
            int step = bfs(forest, ex, ey, a, b);
            if (step == -1) return -1;
            sum += step;
            ex = a; ey = b;
        }
        return sum;
    }

    private int bfs (List<List<Integer>> forest, int ex, int ey, int a, int b) {
        if (ex == a && ey == b) return 0;
        int m = forest.size(), n = forest.get(0).size();
        boolean[][] vis = new boolean[51][51];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{ex, ey});
        vis[ex][ey] = true;
        int step = 0;
        while (!q.isEmpty()) {
            int sz = q.size();
            step++;
            while (sz-- != 0) {
                int[] tmp = q.poll();
                int cur1 = tmp[0], cur2 = tmp[1];
                for (int i = 0; i < 4; i++) {
                    int x = cur1 + dx[i], y = cur2 + dy[i];
                    if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && forest.get(x).get(y) != 0) {
                        if (x == a && y == b) return step;
                        q.add(new int[]{x, y});
                        vis[x][y] = true;
                    }
                }
            }
        }
        return  -1;
    }
}
